/**
 * 918.环形子数组的最大和
 */
public class Exerciser2 {
    public int maxSubarraySumCircular(int[] nums) {
        // 分成两种情况：
        // 1. 最大值在数组中，而非在尾部和头部相连在一起的节点
        // 2. 是头尾相连的节点的部分，那么利用数组和不变，再求数组中的最小值，进行把最小值减掉剩下的就是最大值
        // 所以这个题就可以求 最大和 和 最小和
        int n = nums.length;
        int[] f = new int[n + 1]; // 最大子数组和
        int[] g = new int[n + 1]; // 最小子数组和
        f[0] = g[0] = 0; //初始化
        int sum = 0;
        int fmax = Integer.MIN_VALUE; // f中求最大和中的 最大子数组和
        int gmin = Integer.MAX_VALUE; // g中求最小和中的 最小子数组和
        for(int i = 1;i <= n;i++) {
            int x = nums[i - 1];
            f[i] = Math.max(nums[i - 1],f[i - 1] + nums[i - 1]);
            fmax = Math.max(fmax,f[i]);
            g[i] = Math.min(nums[i - 1],g[i - 1] + nums[i - 1]);
            gmin = Math.min(gmin,g[i]);
            sum += x;
        }
        // 如果 数组全为负数的话，那么gmin == sum,如果进行相减的话，值为0，但是fmax是一个负数，但是返回的需要时fmax，所以这里需要进行判断
        return gmin == sum ? fmax : Math.max(fmax,sum - gmin);
    }
}
